Masala #0538

Sizga uzunligi $n$ ga teng bo’lgan $a$ massiv berilgan. Sizning vazifangiz quyidagi operatsiya bir marta bajarilgach erishish mumkin bo’lgan maksimal qism-massiv yig’indisini topishdir.

• Massivdan qandaydir qism-massiv tanlab undagi barcha elementlarni qiymatini 0 ga aylantiring.

Birinchi qatorda sizga $t$ – testlar soni beriladi. $(1 ≤ t ≤ 2*10^4)$. Keyingi $t$ ta qatorning har birida sizda:

• Birinchi qatorida sizga $n$ – massiv uzunligi beriladi. $(1 ≤ n ≤ 5*10^5)$
• Ikkinchi qatorda sizga $n$ ta son – massiv elementlari beriladi. Massiv elementari $10^9$ dan oshmaydi.

$t$ ta qatorning har biriga faqatgina bitta son – erishish mumkin bo’lgan qism-massivning maksimal summani chiqaring.